import functools


class Solution(object):
    def largestSumOfAverages(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: float
        """
        n = len(nums)
        prefix = [0] * (n + 1)
        for i in range(1, n + 1):
            prefix[i] = prefix[i - 1] + nums[i - 1]

        @functools.cache
        def cut(left, right, k):
            if k == 1:
                return (prefix[right + 1] - prefix[left]) / (right - left + 1)
            max_val = -float('inf')
            for i in range(left, right - k + 2):
                max_val = max((prefix[i + 1] - prefix[left]) / (i - left + 1) + cut(i + 1, right, k - 1), max_val)
            return max_val

        return cut(0, n - 1, k)


data = Solution()
nums = [9, 1, 2, 3, 9]
k = 3
print(data.largestSumOfAverages(nums, k))
nums = [1, 2, 3, 4, 5, 6, 7]
k = 4
print(data.largestSumOfAverages(nums, k))
